1. Field of the Invention
The disclosure relates to a method, system, and article of manufacture for the traversal of empty regions in a searchable data structure, more specifically in a range clustered table.
2. Background
A range clustered table is a table whose data is tightly clustered across one or more columns in the table, i.e., range clustered tables may cluster rows in a table. In the table layout scheme of a range clustered table, each record in the table may have a predetermined record identifier which is an internal identifier used to locate a record in the table. Each record in a range clustered table has a predetermined offset from the logical start of the table, which allows rapid access to the data. As a result, data in range clustered tables can be accessed without needing an index. Range clustered tables are the subject of U.S. patent application Ser. No. 10/429,819 filed May 5, 2003 and entitled “Range-Clustered Tables in a Database Management System”, which is incorporated by reference in its entirety.
Applications in which tightly clustered sequence key ranges are likely may use range clustered tables. A key may be used to generate the logical location of a row in a range clustered table. At table creation time, there are no records in the range clustered table. Space for the range clustered table is preallocated and reserved for use by the table even when records for the table are not filled in. The preallocation of the space for the range clustered table may be based on the record size and the maximum number of records to be stored in the range clustered table.
Range clustered tables have range scan capabilities that require a range scan of the table to examine every possible row which could exist in a query range. When a large number of empty rows exist in a range clustered table, range scanning capabilities may result in large amount of input/output (I/O) operations and locking in order to lock and traverse empty regions of the range clustered table.